package com.demo.java.OD401_450.OD411;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【小明找位置(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146253983
 */
public class OdMain {
    // 二分查找插入位置
    public static int findInsertPosition(int[] sortedNumbers, int target) {
        int left = 0;
        int right = sortedNumbers.length - 1;

        // 使用二分查找
        while (left <= right) {
            int mid = (left + right) / 2;
            // 如果目标值小于中间值，则在左侧查找
            if (sortedNumbers[mid] < target) {
                left = mid + 1;
            }
            // 如果目标值大于中间值，则在右侧查找
            else if (sortedNumbers[mid] > target) {
                right = mid - 1;
            }
            // 如果找到目标值，则返回该位置
            else {
                return mid;
            }
        }

        // 如果没有找到目标值，返回插入的位置
        return left;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入已排好序的学号列表
        String[] numbersInput = scanner.nextLine().split(",");
        int[] sortedNumbers = new int[numbersInput.length];
        // 转换为整数数组
        for (int i = 0; i < numbersInput.length; i++) {
            sortedNumbers[i] = Integer.parseInt(numbersInput[i]);
        }

        // 输入小明的学号
        int targetNumber = scanner.nextInt();

        // 使用二分查找找到小明应该插入的位置
        int position = findInsertPosition(sortedNumbers, targetNumber);

        // 输出位置（从1开始）
        System.out.println(position + 1);
    }
}
